1. Field of the Invention
The present invention relates to a decoding method of and a decoding device for decoding an error correcting code.
2. Description of Related Art
A low-density parity-check code (referred to as an LDPC code from here on) is an error correcting code defined by an m×n matrix in which 1s are scattered. This matrix is referred to as a check matrix. A Sum-Product decoding method was devised as a decoding method of decoding an LDPC code in the 1960s. However, while the Sum-Product decoding method has a high decoding performance, the Sum-Product decoding method requires a large amount of arithmetic operations and it is difficult to implement a circuit for the Sum-Product decoding method. In contrast with this, an Offset BP-based decoding method described in nonpatent reference 1 reduces the amount of arithmetic operations greatly by carrying out calculations approximate to that based on the Sum-Product decoding method.
First, concrete arithmetic operations carried out according to the Sum-Product decoding method will be explained. The algorithm of this decoding method consists of two arithmetic operations which are referred to as a row arithmetic operation and a column arithmetic operation, and decoding is carried out by repeating these arithmetic operations alternately according to the algorithm. The row arithmetic operation is performed on each row of the check matrix. A set of the numbers of columns in each of which the element is equal to 1 in the r-th row of the check matrix is expressed as N(r). For each column c whose number is included in N(r), a row log-likelihood ratio (referred to as an LLR from here on) εr,c is calculated according to the following equation (1).
                              ɛ                      r            ,            c                          =                              (                                          ∏                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              /                                          {                      c                      }                                                                                  ⁢                                                          ⁢                              sgn                ⁡                                  (                                      z                                          r                      ,                                              c                        ′                                                                              )                                                      )                    ·                      (                                          ⊗                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              ⁢                    \                    ⁢                                          {                      c                      }                                                                                  ⁢                                                                z                                      r                    ,                                          c                      ′                                                                                                            )                                              (        1        )            zr,c is a column LLR calculated through the column arithmetic operation which will be explained below, and λc which is an LLR which is calculated for each bit from the received sequence is stored as zr,c during the first iteration of the row arithmetic operation. c′ shows a column other than the column c, having a column number included in N(r).
The definitions of symbols of operation in the above-mentioned equation (1) are as shown in the following equations (2) to (5).
                              sgn          ⁡                      (            x            )                          =                  {                                                    1                                                              (                                      x                    ≥                    0                                    )                                                                                                      -                  1                                                                              (                                      x                    <                    0                                    )                                                                                        (        2        )                                                      ⊗                          i              ∈              I                                ⁢                      z            i                          =                                            z              1                        ⊗                          z              2                        ⊗                                                  ⁢            …            ⁢                                                  ⊗                          z                                              I                                                              ⁢                                          ⁢                      (                          I              =                              {                                  1                  ,                  2                  ,                  …                  ⁢                                                                          ,                                                          I                                                                      }                                      )                                              (        3        )                                          x          ⊗          y                =                  f          ⁡                      (                                          f                ⁡                                  (                  x                  )                                            +                              f                ⁡                                  (                  y                  )                                                      )                                              (        4        )                                          f          ⁡                      (            x            )                          =                  ln          ⁢                                                    exp                ⁡                                  (                  x                  )                                            +              1                                                      exp                ⁡                                  (                  x                  )                                            -              1                                                          (        5        )            
Next, the column arithmetic operation will be explained. A column LLR zr,c is calculated from the row LLR εr,c determined through the row arithmetic operation by using the following equation (6).
                              z                      r            ,            c                          =                              λ            c                    +                                    ∑                                                r                  ′                                ∈                                                      M                    ⁡                                          (                      c                      )                                                        ⁢                  \                  ⁢                                      {                    r                    }                                                                        ⁢                          ɛ                                                r                  ′                                ,                c                                                                        (        6        )            λc is the above-mentioned LLR. A set of the numbers of rows in each of which the element is equal to 1 in the c-th column of the check matrix is expressed as M(c). r′ shows a row other than the row r, having a row number included in M(c).
An estimation of the transmission bits is carried out by using the following equation (7).
                              z          c                =                              λ            c                    +                                    ∑                              r                ∈                                  M                  ⁡                                      (                    c                    )                                                                        ⁢                          ɛ                              r                ,                c                                                                        (        7        )            When zc is zero or more in the result of an arithmetic operation according to the above equation (7), it is estimated that the c-th bit of the received sequence is 1, whereas when zc is smaller than zero, it is estimated that the c-th bit of the received sequence is 0.
Whether or not the estimated bit sequence is a codeword can be determined by using a parity check. Unless the estimated bit sequence is a codeword, the row arithmetic operation is carried out by using the column LLRs calculated through the column arithmetic operation, and, after that, the arithmetic operations explained until now are redone. When the number of times that the arithmetic operations have been iterated reaches its upper limit or when the estimated bit sequence is a codeword, the estimated bit sequence is outputted and the decoding is ended. In the Sum-Product decoding method, the row arithmetic operation shown by the above-mentioned equation (1) requires a huge amount of arithmetic operations.
In accordance with the Offset BP-based decoding method disclosed in nonpatent reference 1, a row arithmetic operation according to the following equation (8) is carried out on instead of that according to the above-mentioned equation (1).
                              ɛ                      r            ,            c                          =                                            (                                                ∏                                                            c                      ′                                        ∈                                                                  N                        ⁡                                                  (                          r                          )                                                                    ⁢                      \                      ⁢                                              {                        c                        }                                                                                            ⁢                                                                  ⁢                                  sgn                  (                                      z                                          r                      ,                                              c                        ′                                                                              )                                            )                        ·            max                    ⁢                      {                                                                                min                                                                  c                        ′                                            ∈                                                                        N                          ⁡                                                      (                            r                            )                                                                          ⁢                        \                        ⁢                                                  {                          c                          }                                                                                                      ⁢                                      {                                                                                        z                                                  r                          ,                                                      c                            ′                                                                                                                                      }                                                  -                α                            ,              0                        }                                              (        8        )            An offset α is a constant calculated for each check matrix, and α providing the highest decoding performance is calculated by using a density evolution method. In accordance with the Offset BP-based decoding method, what is necessary is just to determine a minimum and subtract the offset α from the minimum, and the amount of arithmetic operations of the row arithmetic operation can be reduced greatly.
Although it is already said that the Offset BP-based decoding method include arithmetic operations approximate to those of the Sum-Product decoding method, the approximate arithmetic operations will be explained below in more detail. It is known that a dyadic (or binary) operation defined by the above-mentioned equation (4) which appears in the row arithmetic operation is equivalent to the following equation (9).xy=min{x,y}−ln(1+exp(−|x−y|))+ln(1+exp(−(x+y)))  (9)
In accordance with the Offset BP-based decoding method, a logarithmic function of the second and subsequent terms of the above-mentioned equation (9) is acquired by approximating the logarithmic function by the constant α. In the above-mentioned equation (1) for use in the row arithmetic operation based on the Sum-Product decoding method, a recursive operation (i.e., an arithmetic operation shown by the above-mentioned equation (3)) is included, the approximation calculation including the influence of this recursive operation into the constant α is shown by the above-mentioned equation (8) for use in the row arithmetic operation based on the Offset BP-based decoding method.    [Nonpatent reference 1] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Y. Hu, “Reduced-Complexity Decoding of LDPC Codes”, IEEE Trans. Communications, vol. 53, issue 8, pp. 1288-1299, August 2005.
As mentioned above, in accordance with the Offset BP-based decoding method, the logarithmic function and the influence of the recursive operation are approximated by the constant α. However, actual numerical values which are calculated in accordance with the Sum-Product decoding method change largely and dependently upon variables in the row arithmetic operation. Therefore, a problem with the Offset BP-based decoding method is that the precision of the approximate calculation is low and the decoding performance is not adequate.